package com.sam.book.tree;


/**
 * Created by samwang on 2017/12/23.
 */
public class BinarySearchTree<E extends Comparable<? super E>> {
    private BinaryNode<E> root;

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(E e) {
        return contains(e, root);
    }

    private boolean contains(E element, BinaryNode<E> node) {
        if (node == null) {
            return false;
        }
        int compare = element.compareTo(node.element);
        if (compare == 0) {
            return true;
        } else {
            return contains(element, compare > 0 ? node.right : node.left);
        }

    }

    public E findMin() {
        if (isEmpty()) {
            throw new RuntimeException("tree is empty");
        }
        return findMin(root).element;
    }

    public E findMax() {
        if (isEmpty()) {
            throw new RuntimeException("tree is empty");
        }
        return findMax(root).element;
    }

    public void insert(E e) {
        root = insert(e, root);
    }

    public void remove(E e) {
        root = remove(e, root);
    }


    private BinaryNode<E> findMin(BinaryNode<E> node) {
        if (node.left != null) {
            return findMin(node.left);
        }
        return node;
    }
    private BinaryNode<E> findMax(BinaryNode<E> node) {
        //递归实现
//        if (node.right != null) {
//            return findMax(node.right);
//        }

        //非递归实现
        while (node.right != null) {
            node = node.right;
        }

        return node;
    }

    private BinaryNode<E> insert(E element, BinaryNode<E> node) {
        if (node == null) {
            return new BinaryNode<>(element);
        }

        int compare = element.compareTo(node.element);
        if (compare == 0) {
            return node;//插入失败,不处理相同元素插入
        } else if (compare > 0) {
            node.right = insert(element, node.right);
        } else {
            node.left = insert(element, node.left);
        }

        return node;
    }

    /**
     * 移除后要将其子节点链到树中
     * @param element
     * @param node
     * @return
     */
    private BinaryNode<E> remove(E element, BinaryNode<E> node) {
        if (node == null) {
            return null;//不存在该元素，无需删除
        }

        int compare = element.compareTo(node.element);
        if (compare == 0) {
            if (node.left != null && node.right != null) {
                //被移除的节点左右都有节点，右子节点代替当前节点，左子节点放在右子节点最小节点的左节点
                findMin(node.right).left = node.left;
                node = node.right;
            } else {
                node = node.left == null ? node.right : node.left;
            }

            return node;
        } else if (compare > 0) {
            node.right = remove(element, node.right);
        } else {
            node.left = remove(element, node.left);
        }

        return node;
    }



    public static class BinaryNode<T> {
        public BinaryNode(T element) {
            this.element = element;
        }

        T element;
        BinaryNode<T> left;
        BinaryNode<T> right;

        @Override
        public String toString() {
            return "{" +
                    "val=" + element +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
}
